package tree;

/**
 * @author kaho
 * @since 2021/2/26
 */
public class _129_求根到叶子节点数字之和 {

    /**
     * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
     *
     * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
     *
     * 计算从根到叶子节点生成的所有数字之和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root
     * @return
     */
    public static int sumNumbers2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs2(root, 0);
    }

    private static int dfs2(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }
        i = i*10+ root.val;
        if (root.left == null && root.right == null) {
            return i;
        }
        return dfs2(root.left, i) + dfs2(root.right, i);
    }


    public static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs1(root, 0);

    }

    private static int dfs1(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }
        int val = root.val;
        i = i*10 +val;
        if (root.left == null && root.right == null) {
            return i;
        }
        return dfs1(root.left ,i)+ dfs1(root.right, i);
    }

    public static int sumNumbers1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int result = 0;
        return dfs(root, new StringBuilder(),result);
    }

    private static int dfs(TreeNode root, StringBuilder cur, int result) {
        if (root == null) {
            return result;
        }
        int val = root.val;
        cur.append(val);
        if (root.left ==null && root.right ==null) {
            result = result + Integer.parseInt(cur.toString());
            return result;
        }
        result = dfs(root.left, cur, result);
        if (root.left!=null && cur.length()!=0){
            cur.deleteCharAt(cur.length()-1);
        }
        result = dfs(root.right, cur, result);
        if (root.right!=null&& cur.length()!=0){
            cur.deleteCharAt(cur.length()-1);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(0);
        treeNode1.left = treeNode2;
        int i = sumNumbers(treeNode1);
    }
}
